{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Friends Of Appropriate Ages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numFriendRequests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #适龄的朋友"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在社交媒体网站上有 <code>n</code> 个用户。给你一个整数数组 <code>ages</code> ，其中 <code>ages[i]</code> 是第 <code>i</code> 个用户的年龄。</p>\n",
    "\n",
    "<p>如果下述任意一个条件为真，那么用户 <code>x</code> 将不会向用户 <code>y</code>（<code>x != y</code>）发送好友请求：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>ages[y] &lt;= 0.5 * ages[x] + 7</code></li>\n",
    "\t<li><code>ages[y] &gt; ages[x]</code></li>\n",
    "\t<li><code>ages[y] &gt; 100 &amp;&amp; ages[x] &lt; 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>否则，<code>x</code> 将会向 <code>y</code> 发送一条好友请求。</p>\n",
    "\n",
    "<p>注意，如果 <code>x</code> 向 <code>y</code> 发送一条好友请求，<code>y</code> 不必也向 <code>x</code> 发送一条好友请求。另外，用户不会向自己发送好友请求。</p>\n",
    "\n",
    "<p>返回在该社交媒体网站上产生的好友请求总数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ages = [16,16]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>2 人互发好友请求。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ages = [16,17,18]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>产生的好友请求为 17 -&gt; 16 ，18 -&gt; 17 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ages = [20,30,100,110,120]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>产生的好友请求为 110 -&gt; 100 ，120 -&gt; 110 ，120 -&gt; 100 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == ages.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= ages[i] &lt;= 120</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [friends-of-appropriate-ages](https://leetcode.cn/problems/friends-of-appropriate-ages/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [friends-of-appropriate-ages](https://leetcode.cn/problems/friends-of-appropriate-ages/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[16,16]', '[16,17,18]', '[20,30,100,110,120]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        res = 0  # 保存结果数量\n",
    "       \n",
    "        line = [0]*121\n",
    "        for x in ages:  #统计次数\n",
    "            line[x] += 1\n",
    "\n",
    "        # 统计120个数字每个数字需要发送的请求数之和，即为答案\n",
    "        for i in range(15,121):  # 因为<=14的数不会向任何人发请求也不会被发请求\n",
    "            if not line[i]:  # 如果目前数字没出现，即0次，跳过\n",
    "                continue\n",
    "            else:  # 目前数字出现\n",
    "                tp = -1  # 用来记录目前的一个数字发送的请求数（初始值设为-1因为不包括这一个数字自己）         \n",
    "#初始值为-1 是为了同一个数字重复多次出现时，互相之间除去自身 如[16,16,16] 应为3个数*每个数发2（3-1）次 \n",
    "                for j in range(i // 2 + 8, i + 1):  # 排除条件1和条件2的范围，除前也除后\n",
    "                    tp += line[j]\n",
    "                res += line[i]*tp  # 目前数字出现的次数 * 一个数字需要发送请求数\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        cnts = collections.Counter(ages)\n",
    "        vals = [[key, cnts[key]] for key in cnts]\n",
    "        vals.sort()\n",
    "        ed = ans = total = 0\n",
    "        n = len(vals)\n",
    "        stack = collections.deque()\n",
    "        for age, cnt in vals:\n",
    "            if age <= 14: continue\n",
    "            while ed < n and 0.5 * vals[ed][0] + 7 < age:\n",
    "                total += vals[ed][1]\n",
    "                stack.append(vals[ed])\n",
    "                ed += 1\n",
    "            while stack and stack[0][0] < age:\n",
    "                total -= stack.popleft()[1]\n",
    "            ans += (total - 1) * cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        cnt = [0] * 121\n",
    "        for age in ages:\n",
    "            cnt[age] += 1\n",
    "        pre = [0] * 121\n",
    "        for i in range(1, 121):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(15, 121):\n",
    "            if cnt[i] > 0:\n",
    "                bound = int(i * 0.5 + 8)\n",
    "                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        cnt = Counter(ages)\n",
    "        ans = 0\n",
    "        pre = [0] * 121\n",
    "        for i in range(1, 121):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        for i in range(15, 121):\n",
    "            if cnt[i]:\n",
    "                x = int(i * 0.5) + 8\n",
    "                ans += cnt[i] * (pre[i] - pre[x - 1] - 1)\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        cnt = [0] * 121\n",
    "        for age in ages:\n",
    "            cnt[age] += 1\n",
    "\n",
    "        pre = [0] * 121\n",
    "        for i in range(1, 121):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "\n",
    "        res = 0\n",
    "        for age in range(15, 121):\n",
    "            if cnt[age] == 0: continue\n",
    "            res += cnt[age] * (pre[age] - pre[age // 2 + 7] - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        cnt = [0] * 121\n",
    "        for a in ages:\n",
    "            cnt[a] += 1\n",
    "\n",
    "        pre = [0] * 121\n",
    "        for i in range(1, 121):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(15, 121):\n",
    "            if cnt[i] > 0:\n",
    "                bound = int(i * 0.5 + 8)\n",
    "                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages) -> int:\n",
    "        res = 0\n",
    "        ct_ages = [0]*121\n",
    "        for age in ages:\n",
    "            ct_ages[age] += 1\n",
    "        pre = [0]*121\n",
    "        for i in range(1, 121):\n",
    "            pre[i] = pre[i-1] + ct_ages[i]\n",
    "        for i in range(15, 121):\n",
    "            if ct_ages[i] > 0:\n",
    "                low = int(0.5*i+8)\n",
    "                res += ct_ages[i]*(pre[i]-pre[low-1]-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        tmp = [0] * 121\n",
    "        res = 0\n",
    "        age_dict = {}\n",
    "        for age in ages:\n",
    "            tmp[age] += 1\n",
    "\n",
    "        for x in range(15, 121):\n",
    "            if not tmp[x]:\n",
    "                continue\n",
    "            m = -1\n",
    "            for y in range(x//2 + 8, x +1):\n",
    "                m += tmp[y]\n",
    "            res += tmp[x] * m\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ages.sort(reverse = True)\n",
    "        ans = 0\n",
    "        for i,x in enumerate(ages):\n",
    "            if i > 0 and x == ages[i - 1] and x*0.5 > 7:\n",
    "                t -= 2\n",
    "                ans += t\n",
    "                continue\n",
    "            t = 0\n",
    "            for j,y in enumerate(ages[i + 1:]):\n",
    "                if y <= 0.5 * x + 7:\n",
    "                    break\n",
    "                t += 1 if x != y else 2\n",
    "            ans += t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        cnts = collections.Counter(ages)\n",
    "        vals = [[key, cnts[key]] for key in cnts]\n",
    "        vals.sort()\n",
    "        ed = ans = total = 0\n",
    "        n = len(vals)\n",
    "        stack = collections.deque()\n",
    "        for age, cnt in vals:\n",
    "            if age <= 14: continue\n",
    "            while ed < n and 0.5 * vals[ed][0] + 7 < age:\n",
    "                total += vals[ed][1]\n",
    "                stack.append(vals[ed])\n",
    "                ed += 1\n",
    "            while stack and stack[0][0] < age:\n",
    "                total -= stack.popleft()[1]\n",
    "            ans += (total - 1) * cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        people = sorted(Counter(ages).items())[::-1]\n",
    "        ans = 0\n",
    "        n = len(people)\n",
    "        for i in range(n):\n",
    "            if people[i][0] <= 14:\n",
    "                pass\n",
    "            else:\n",
    "                ans += people[i][1] * (people[i][1] - 1)\n",
    "            for j in range(i + 1,n):\n",
    "                if people[j][0] > people[i][0] * 0.5 + 7:\n",
    "                    ans+= people[i][1] * people[j][1]\n",
    "                else:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        mapping = {}\n",
    "        for age in ages:\n",
    "            if(age not in mapping):\n",
    "                mapping[age] = 1\n",
    "            else:\n",
    "                mapping[age] += 1\n",
    "        result = 0\n",
    "        for age in mapping:\n",
    "            if(age > 14):\n",
    "                result += (mapping[age]-1)*mapping[age]\n",
    "        \n",
    "        ageSort = sorted(mapping.keys())\n",
    "        for i in range(len(ageSort)):\n",
    "            x = ageSort[i]\n",
    "            for j in range(i-1,-1,-1):\n",
    "                y = ageSort[j]\n",
    "                if(x >= 2*y-14):\n",
    "                    break\n",
    "                if(x < 2*y-14 and x >= y and (y<=100 or x>=100)):\n",
    "                    result += mapping[x]*mapping[y]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        n = len(ages)\n",
    "        ans = 0\n",
    "        ages.sort()\n",
    "        left = 0\n",
    "        right = 0\n",
    "        ans = 0\n",
    "        for age in ages:\n",
    "            while left < n and ages[left] <= 0.5 * age + 7:\n",
    "                left += 1\n",
    "            while right < n and ages[right] <= age:\n",
    "                right += 1\n",
    "            if right > left:\n",
    "                ans += (right - left - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        cnt = [0] * 121\n",
    "        for age in ages:\n",
    "            cnt[age] += 1\n",
    "        pre = [0] * 121\n",
    "        for i in range(1, 121):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(15, 121):\n",
    "            if cnt[i] > 0:\n",
    "                bound = int(i * 0.5 + 8)\n",
    "                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        #copy\n",
    "        cnt = [0] * (max(ages)+1)\n",
    "        for age in ages:\n",
    "            cnt[age] += 1\n",
    "        presum = [0] + list(accumulate(cnt))\n",
    "        return sum(cnt[age]*max(0,presum[age+1]-presum[age//2+8]-1) for age in set(ages))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ages.sort()\n",
    "        l = r = 0\n",
    "        res = 0\n",
    "        for x in ages:\n",
    "            if x < 15:\n",
    "                continue\n",
    "            while ages[l] <= x // 2 + 7:\n",
    "                l += 1\n",
    "            while r + 1 < len(ages) and ages[r+1] <= x:\n",
    "                r += 1\n",
    "            res += r - l \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        n = max(ages)\n",
    "        cnt = [0]*(n + 1)\n",
    "        for x in ages:\n",
    "            cnt[x] += 1\n",
    "        pre = list(accumulate(cnt,initial = 0))\n",
    "        \n",
    "        return sum(cnt[i]*(pre[i + 1] - pre[i//2 + 8] - 1) for i in range(15,n + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        cnt = [0] * 121\n",
    "        for age in ages:\n",
    "            cnt[age] += 1\n",
    "        pre = [0] * 121\n",
    "        for i in range(1, 121):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(15, 121):\n",
    "            if cnt[i] > 0:\n",
    "                bound = int(i * 0.5 + 8)\n",
    "                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        n = len(ages)\n",
    "        ages.sort()\n",
    "        left = right = ans = 0\n",
    "        for age in ages:\n",
    "            if age < 15:\n",
    "                continue\n",
    "            while ages[left] <= 0.5 * age + 7:\n",
    "                left += 1\n",
    "            while right + 1 < n and ages[right + 1] <= age:\n",
    "                right += 1\n",
    "            ans += right - left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        n = len(ages)\n",
    "        left = right = ans = 0\n",
    "        ages.sort()\n",
    "        for age in ages:\n",
    "            if age < 15:\n",
    "                continue\n",
    "            while ages[left] <= 0.5 * age + 7:\n",
    "                left += 1\n",
    "            while right + 1 < n and ages[right + 1] <= age:\n",
    "                right += 1\n",
    "            ans += right - left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        cnts = [0] * (max(ages) + 1)\n",
    "        for age in ages:\n",
    "            cnts[age] += 1\n",
    "        presum = [0] + list(accumulate(cnts))\n",
    "        return sum(cnts[age] * max(0, presum[age + 1] - presum[age//2 + 8] - 1) for age in set(ages))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        n = len(ages)\n",
    "        ages.sort()\n",
    "        left = right = ans = 0\n",
    "        for i, age in enumerate(ages):\n",
    "            if age < 15:\n",
    "                continue\n",
    "            while ages[left] <= 0.5 * age + 7:\n",
    "                left += 1\n",
    "            while right + 1 < n and ages[right + 1] <= age:\n",
    "                right += 1\n",
    "            ans += right - left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ans = 0\n",
    "        ages.sort()\n",
    "        n = len(ages)\n",
    "        for i in range(n):\n",
    "            y = ages[i]\n",
    "            pos1 = bisect_left(ages, y) + 1\n",
    "            pos2 = bisect_right(ages, 2 * (y - 7) - 1)\n",
    "            if y > 100 and pos1 < n and ages[pos1] < 100:\n",
    "                continue\n",
    "            ans += pos2 - pos1 if pos2 - pos1 > 0 else 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: [int]) -> int:\n",
    "        ages.sort()\n",
    "        nm=len(ages)\n",
    "        tot=0\n",
    "        for p in range(nm):\n",
    "            left=0.5 * ages[p]+7      #必须大于这个\n",
    "            if left>float(ages[p]): continue\n",
    "            leftidx=bisect.bisect_right(ages,left)\n",
    "            rightidx=bisect.bisect_right(ages,ages[p])\n",
    "            nums=rightidx-leftidx-1\n",
    "            if nums>=0:\n",
    "                tot+=nums\n",
    "\n",
    "\n",
    "        return tot\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        n = len(ages)\n",
    "        ages.sort()\n",
    "        res = 0\n",
    "        left, right = 0,0\n",
    "        for age in ages:\n",
    "            if age<15:\n",
    "                continue\n",
    "            while ages[left]<=0.5*age + 7:\n",
    "                left += 1\n",
    "            while right+1<n and ages[right+1]<=age:\n",
    "                right += 1\n",
    "            res += right-left\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    第一想法 拓扑排序  X\n",
    "    \n",
    "    最好做法 计数加前缀和\n",
    "\"\"\"\n",
    " \n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "\n",
    "\n",
    "        cnt = [0] * 121\n",
    "        for x in ages:\n",
    "            cnt[x] += 1\n",
    "        presum = list(accumulate(cnt,initial=0))\n",
    "        # print(len(presum))\n",
    "        return sum(cnt[age]*max(0,presum[age+1]-presum[age//2+8]-1) for age in set(ages))\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        tmp = [0] * 121\n",
    "        res = 0\n",
    "        age_dict = {}\n",
    "        for age in ages:\n",
    "            tmp[age] += 1\n",
    "\n",
    "        for x in range(15, 121):\n",
    "            if not tmp[x]:\n",
    "                continue\n",
    "            m = -1\n",
    "            for y in range(x//2 + 8, x +1):\n",
    "                m += tmp[y]\n",
    "            res += tmp[x] * m\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        mp={}\n",
    "        for x in ages:\n",
    "            if x in mp:\n",
    "                mp[x]+=1\n",
    "            else:\n",
    "                mp[x]=1\n",
    "        ans=0\n",
    "        for k,num in mp.items():\n",
    "            if k<=14:\n",
    "                continue\n",
    "            ans+=num*(num-1)\n",
    "        ages=sorted(list(set(ages)),reverse=True)  \n",
    "        n=len(ages) \n",
    "        for i in range(n-1):\n",
    "            age=ages[i]\n",
    "            j=i+1\n",
    "            while j<n and ages[j]>0.5*age+7:\n",
    "                ans+=mp[age]*mp[ages[j]]\n",
    "                j+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ages.sort()\n",
    "        res = x = y = 0\n",
    "        for age in ages:\n",
    "            if age < 15:\n",
    "                continue\n",
    "            while ages[y] <= age / 2 + 7:\n",
    "                y += 1\n",
    "            x = max(x, y)\n",
    "            while x + 1 < len(ages) and ages[x + 1] <= age:\n",
    "                x += 1\n",
    "            res += x - y\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        counter = Counter(ages)\n",
    "        dages = list(counter.keys())\n",
    "        dages.sort(reverse=True)\n",
    "        n = len(dages)\n",
    "        ans = 0\n",
    "        for x in range(n):\n",
    "            if dages[x] > 14:\n",
    "                m = counter[dages[x]]\n",
    "                ans += m * (m - 1)\n",
    "            for y in range(x + 1, n):\n",
    "                if dages[x] + 14 < dages[y] * 2 and not (\n",
    "                    dages[x] < 100 and dages[y] > 100\n",
    "                ):\n",
    "                    ans += counter[dages[x]] * counter[dages[y]]\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    # assert 2 == Solution().numFriendRequests([16, 16])\n",
    "    # assert 2 == Solution().numFriendRequests([16, 17, 18])\n",
    "    # assert 3 == Solution().numFriendRequests([20, 30, 100, 110, 120])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        cnt = [0] * 121\n",
    "        for age in ages:\n",
    "            cnt[age] += 1\n",
    "        pre = [0] * 121\n",
    "        for i in range(1, 121):\n",
    "            pre[i] = pre[i - 1] + cnt[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(15, 121):\n",
    "            if cnt[i] > 0:\n",
    "                bound = int(i * 0.5 + 8)\n",
    "                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ages.sort()\n",
    "        res = 0\n",
    "        left = right = 0\n",
    "        for age in ages:\n",
    "            if age < 15:\n",
    "                continue  \n",
    "            while ages[left] <= age * 0.5 + 7:\n",
    "                left += 1\n",
    "            while right < len(ages) and ages[right] <= age:\n",
    "                right += 1\n",
    "            res += right - left -1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        MAX_AGE = 130\n",
    "        counts = [0] * MAX_AGE\n",
    "        for age in ages:\n",
    "            counts[age] += 1\n",
    "        for i in range(1, MAX_AGE):\n",
    "            counts[i] += counts[i - 1]\n",
    "        sending = ans = 0\n",
    "        for beSent in range(1, MAX_AGE):\n",
    "            beSentCount = counts[beSent] - counts[beSent - 1]\n",
    "            if not beSentCount:\n",
    "                continue\n",
    "            if sending < beSent:\n",
    "                sending = beSent\n",
    "            while sending < MAX_AGE and beSent > 0.5 * sending + 7:\n",
    "                sending += 1\n",
    "            sendingCount = counts[sending - 1] - counts[beSent - 1] - 1\n",
    "            ans += beSentCount * sendingCount if sendingCount > 0 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "\n",
    "        count = [0] * 121\n",
    "        pre_sum = [0] * 121\n",
    "\n",
    "        for age in ages:\n",
    "            count[age] += 1\n",
    "        \n",
    "        for i in range(1, 121):\n",
    "            pre_sum[i] = count[i] + pre_sum[i-1]\n",
    "        \n",
    "        ret = 0\n",
    "        for age, num in enumerate(count):\n",
    "\n",
    "            mn = floor(0.5 * age + 7)\n",
    "            mx = age\n",
    "\n",
    "            people = pre_sum[mx] - pre_sum[mn] - 1\n",
    "            if people > 0:\n",
    "\n",
    "                ret += people * num\n",
    "\n",
    "        \n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        #copy\n",
    "        cnt = [0] * (max(ages)+1)\n",
    "        for age in ages:\n",
    "            cnt[age] += 1\n",
    "        presum = [0] + list(accumulate(cnt))\n",
    "        return sum(cnt[age]*max(0,presum[age+1]-presum[age//2+8]-1) for age in set(ages))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        n = len(ages)\n",
    "        ages.sort()\n",
    "        left = 0\n",
    "        right = 0\n",
    "        ans = 0\n",
    "        for age in ages:\n",
    "            if age < 15 :\n",
    "                continue\n",
    "            while ages[left] <= 0.5*age + 7:\n",
    "                left += 1\n",
    "            while right < n and ages[right] <= age: \n",
    "                right += 1\n",
    "            ans += right - left - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ages.sort()\n",
    "        n = len(ages)\n",
    "        left = right = res = 0\n",
    "        for age in ages:\n",
    "            if age < 15: \n",
    "                continue\n",
    "            while ages[left] <= 0.5 * age + 7:\n",
    "                left += 1\n",
    "            while right + 1 < n and ages[right + 1] <= age:\n",
    "                right += 1\n",
    "            res += right - left\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        res = 0\n",
    "        ages.sort(reverse=True)\n",
    "        n = len(ages)\n",
    "        info = {}\n",
    "        for i in range(n):\n",
    "            if ages[i] in info:\n",
    "                res += info[ages[i]]\n",
    "                continue\n",
    "            r = n - 1\n",
    "            while i < r:\n",
    "                if ages[r] <= 14 or  ages[i] * 0.5 + 7 >= ages[r]:\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    res += (r-i)\n",
    "                    info[ages[i]] = r - i\n",
    "                    break\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        def judgment(x, y):\n",
    "            val = x * 0.5 + 7\n",
    "            if val >= y or y > x or (y > 100 and x < 100):\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        def binarySearch(i, j, x, nums):\n",
    "            start, end = i, j\n",
    "            while j - i > 3:\n",
    "                mid = (i+j) >> 1\n",
    "                if judgment(x, nums[mid]): i = mid + 1\n",
    "                else: j = mid\n",
    "            for k in range(i, j+1):\n",
    "                if not judgment(x, nums[k]):\n",
    "                    return k-start if k-1 >= start else -1\n",
    "            return end - start + 1\n",
    "\n",
    "        ages.sort(reverse=True)\n",
    "        print(ages)\n",
    "        res = 0\n",
    "        for i in range(len(ages)):\n",
    "            if i and ages[i] == ages[i-1] and val != -1: \n",
    "                res += val\n",
    "                continue\n",
    "            val = binarySearch(i+1, len(ages)-1, ages[i], ages)\n",
    "            # print(ages[i], val)\n",
    "            if val != -1:\n",
    "                res += val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ages.sort()\n",
    "        l = 0\n",
    "        r = 0\n",
    "        res = 0\n",
    "        n = len(ages)\n",
    "        for x in ages:\n",
    "            if x < 15:\n",
    "                continue\n",
    "            while ages[l] <= x // 2 + 7:\n",
    "                l += 1\n",
    "            while r < n and  ages[r] <= x:\n",
    "                r += 1\n",
    "            res += r - l - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ages.sort()\n",
    "        res = x = y = 0\n",
    "        for age in ages:\n",
    "            if age < 15:\n",
    "                continue\n",
    "            while ages[y] <= age / 2 + 7:\n",
    "                y += 1\n",
    "            while x + 1 < len(ages) and ages[x + 1] <= age:\n",
    "                x += 1\n",
    "            res += x - y\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    第一想法 拓扑排序  X\n",
    "    \n",
    "    最好做法 计数加前缀和\n",
    "\"\"\"\n",
    " \n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "\n",
    "\n",
    "        cnt = [0] * 121\n",
    "        for x in ages:\n",
    "            cnt[x] += 1\n",
    "        presum = list(accumulate(cnt,initial=0))\n",
    "        print(len(presum))\n",
    "        return sum(cnt[age]*max(0,presum[age+1]-presum[age//2+8]-1) for age in set(ages))\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        # y <= x < 2y-14\n",
    "        # 2y-14 > y\n",
    "        # y > 14\n",
    "        res = 0\n",
    "        ages.sort()\n",
    "        l, r = 0, 0\n",
    "        while r < len(ages):\n",
    "            while l < r and 2*ages[l]-14 <= ages[r]:\n",
    "                l += 1\n",
    "            res += r-l\n",
    "            r += 1\n",
    "        l, r = 0, 0\n",
    "        while r < len(ages):\n",
    "            if ages[r] != ages[l]:\n",
    "                if 2*ages[l]-14 > ages[r-1]:\n",
    "                    res += (1+r-l-1)*(r-l-1)//2\n",
    "                l = r \n",
    "            r += 1\n",
    "        if 2*ages[l]-14 > ages[r-1]:\n",
    "            res += (1+r-l-1)*(r-l-1)//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        res = 0\n",
    "        ages.sort()\n",
    "        print(ages)\n",
    "        def binary_search(left, right, target):\n",
    "            nonlocal ages\n",
    "            if left > right:\n",
    "                return 0\n",
    "            l,r = left,right\n",
    "            posl,posr = 0,0\n",
    "            while l<=r:\n",
    "                mid = l+(r-l)//2\n",
    "                if ages[mid] <= 0.5*target+7:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    posl = mid\n",
    "                    r = mid-1\n",
    "            l,r = left,right\n",
    "            while l<=r:\n",
    "                mid = l+(r-l)//2\n",
    "                if ages[mid] > target:\n",
    "                    r = mid-1\n",
    "                else:\n",
    "                    posr = mid\n",
    "                    l = mid+1\n",
    "            return posr-posl+1\n",
    "        cnt = -1\n",
    "        for i in range(len(ages)):\n",
    "            if ages[i] <= 14:\n",
    "                cnt = i\n",
    "                continue\n",
    "            res += binary_search(0, len(ages)-1, ages[i])\n",
    "        return res+cnt+1-len(ages)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ages=sorted(ages)\n",
    "        n=len(ages)\n",
    "        ans=0\n",
    "        age_ans={}\n",
    "        for i in range(n):\n",
    "            if ages[i]<15:\n",
    "                continue\n",
    "            low=ages[i]*0.5+7\n",
    "            high=ages[i]\n",
    "            left=i-1\n",
    "            right=i+1\n",
    "            is_100=ages[i]>=100\n",
    "            cur_ans=ans\n",
    "            if ages[i] in age_ans:\n",
    "                ans+=age_ans[ages[i]]\n",
    "                continue\n",
    "            # print(left,right)\n",
    "            if is_100:\n",
    "                while left>=0 and ages[left]>low and ages[left]<=high:\n",
    "                    left-=1\n",
    "                    ans+=1\n",
    "                    \n",
    "                while right<n and ages[right]>low and ages[right]<=high:\n",
    "                    # print(\"gg\",right)\n",
    "                    right+=1\n",
    "                    ans+=1\n",
    "            else:\n",
    "                while left>=0 and ages[left]>low and ages[left]<=high and ages[left]<=100:\n",
    "                    left-=1\n",
    "                    ans+=1\n",
    "                    \n",
    "                while right<n and ages[right]>low and ages[right]<=high and ages[right]<=100:\n",
    "                    # print(\"gg\",right)\n",
    "                    right+=1\n",
    "                    ans+=1\n",
    "            age_ans[ages[i]]=ans-cur_ans\n",
    "\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    第一想法 拓扑排序  X\n",
    "    \n",
    "    最好做法 计数加前缀和\n",
    "\"\"\"\n",
    " \n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "\n",
    "\n",
    "        cnt = [0] * 121\n",
    "        for x in ages:\n",
    "            cnt[x] += 1\n",
    "        presum = [0] + list(accumulate(cnt))\n",
    "        return sum(cnt[age]*max(0,presum[age+1]-presum[age//2+8]-1) for age in set(ages))\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        n=len(ages)\n",
    "        ages.sort()\n",
    "        left,right,ans=0,0,0\n",
    "        for x in ages:\n",
    "            if x<=14:\n",
    "                continue\n",
    "            while left<n and ages[left]<=0.5*x+7:\n",
    "                left+=1\n",
    "            while right<n and ages[right]<=x:\n",
    "                right+=1\n",
    "            ans+=right-left-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    第一想法 拓扑排序  X\n",
    "    \n",
    "    最好做法 计数加前缀和\n",
    "\"\"\"\n",
    " \n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "\n",
    "\n",
    "        cnt = [0] * 121\n",
    "        for x in ages:\n",
    "            cnt[x] += 1\n",
    "        presum = [0]+list(accumulate(cnt))\n",
    "        # print(len(presum))\n",
    "        return sum(cnt[age]*max(0,presum[age+1]-presum[age//2+8]-1) for age in set(ages))\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ages.sort()\n",
    "\n",
    "        xIdx = 0\n",
    "        yLower = 0\n",
    "        yHigher = 0\n",
    "        nRequests = 0\n",
    "\n",
    "        while xIdx < len(ages):\n",
    "            curLower = 0.5 * ages[xIdx] + 7\n",
    "            curHigher = ages[xIdx] + 1\n",
    "\n",
    "            while yLower < len(ages) and ages[yLower] <= curLower:\n",
    "                yLower += 1\n",
    "            \n",
    "            while yHigher < len(ages) and ages[yHigher] < curHigher:\n",
    "                yHigher += 1\n",
    "            yHigher = max(0, yHigher - 1)\n",
    "            if yLower <= yHigher:\n",
    "                nRequests += (yHigher - yLower + 1) - 1\n",
    "            xIdx += 1\n",
    "\n",
    "        return nRequests\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "x \n",
    "valid-interval for each x\n",
    "\n",
    "lower = 0.5 * x + 7 (exclusive)\n",
    "upper = x (inclusive)\n",
    "\n",
    "send to y if\n",
    "\n",
    "0.5 * x + 7 < y <= x\n",
    "\n",
    "sort the ages\n",
    "xIdx\n",
    "yLower, yHigher\n",
    "nRequest = 0\n",
    "while xIdx < len(ages):\n",
    "    curAge = ages[xIdx]\n",
    "    while yLower < len(ages) and ages[ylower] <= 0.5 * curAge + 7\n",
    "        yLower += 1\n",
    "    yHigher = xIdx\n",
    "    nRequest += (yHigher -  yLower + 1) - 1\n",
    "\n",
    "time complexity O(nlogn), n == len(ages)\n",
    "\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        # 模拟一维数组，或者二位数组\n",
    "        # n = len(ages)\n",
    "        # count = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "               \n",
    "        #         if i == j or ages[j] <= 0.5 * ages[i] + 7 or ages[j] > ages[i] or ages[j] > 100 and ages[i] < 100:\n",
    "        #             continue\n",
    "        #         else:\n",
    "        #             count += 1\n",
    "        \n",
    "        # return count\n",
    "        n = len(ages)\n",
    "        ages.sort()\n",
    "        left = right = ans = 0\n",
    "        for age in ages:\n",
    "            if age<15:\n",
    "                continue\n",
    "            while ages[left] <= 0.5 * age + 7:\n",
    "                left += 1\n",
    "            while right +1 < n and ages[right + 1] <= age:\n",
    "                right += 1\n",
    "            ans += right - left\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    第一想法 拓扑排序\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        n = len(ages)\n",
    "        ages.sort()\n",
    "        ans = 0\n",
    "        for i,x in enumerate(ages):\n",
    "            if x<15:continue\n",
    "            l = bisect_right(ages,x//2+7)\n",
    "            r = bisect_right(ages,x)\n",
    "            ans +=r-l-1\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        #排序+双指针\n",
    "        n=len(ages)\n",
    "        ages.sort()\n",
    "        left,right,ans=0,0,0\n",
    "        for x in ages:\n",
    "            if x<=14:\n",
    "                continue\n",
    "            while left<n and ages[left]<=0.5*x+7:\n",
    "                left+=1\n",
    "            while right<n and ages[right]<=x:\n",
    "                right+=1\n",
    "            ans+=right-left-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\r\n",
    "# from collections import coutner\r\n",
    "class Solution:\r\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\r\n",
    "        ages.sort()\r\n",
    "        L=len(ages)\r\n",
    "        ret=0\r\n",
    "\r\n",
    "        cur_cnt=0\r\n",
    "        valid_idx=0\r\n",
    "        while valid_idx<L and ages[valid_idx]<15:\r\n",
    "            valid_idx+=1\r\n",
    "        i=valid_idx+1\r\n",
    "        while i<L:\r\n",
    "            # if ages[i]>=100 and ages[valid_idx]<100:\r\n",
    "            #     valid_idx=i\r\n",
    "            #     i+=1\r\n",
    "            # if i==L:\r\n",
    "            #     break\r\n",
    "            if ages[i]==ages[i-1]:\r\n",
    "                j=i-1\r\n",
    "                while i<L and ages[i]==ages[i-1]:\r\n",
    "                    i+=1\r\n",
    "                sames=i-j\r\n",
    "                ret+=(sames-1)*cur_cnt+sames*(sames-1)\r\n",
    "\r\n",
    "\r\n",
    "            if i==L:\r\n",
    "                break\r\n",
    "            y=ages[i]/2+7\r\n",
    "            yid=bisect.bisect_right(ages,y,lo=valid_idx)\r\n",
    "            cur_cnt=i-yid\r\n",
    "            ret+=cur_cnt\r\n",
    "            i+=1\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        length = len(ages)\n",
    "\n",
    "        left = 0\n",
    "        right = 0\n",
    "        ret = 0\n",
    "        ages.sort()\n",
    "        for age in ages:\n",
    "            if age <= 14:\n",
    "                continue\n",
    "            while left < length and 0.5 * age + 7 >= ages[left]:\n",
    "                left += 1\n",
    "            while right < length and age >= ages[right]:\n",
    "                right += 1\n",
    "            ret += (right - left - 1)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        # y>=0.5x+7 and y<=x\n",
    "        def bisect_right(ages, t, l, r):\n",
    "            while l < r:\n",
    "                mid = (l+r)//2\n",
    "                if ages[mid] > t:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid+1\n",
    "            return l\n",
    "            \n",
    "        ages.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(ages)):\n",
    "            l = bisect_right(ages, 0.5*ages[i]+7, 0, len(ages))\n",
    "            r = bisect_right(ages, ages[i], 0, len(ages)) - 1\n",
    "            # print(f\"l={l}, r={r}\")\n",
    "            ans += max(r-l, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\r\n",
    "        ages.sort()\r\n",
    "        lf, rt = 0, 0\r\n",
    "        ans = 0\r\n",
    "        for age in ages:\r\n",
    "            if age <= 14:\r\n",
    "                continue\r\n",
    "            while lf < len(ages) and ages[lf] <= 0.5 * age + 7:\r\n",
    "                lf += 1\r\n",
    "            while rt < len(ages) and ages[rt] <= age:\r\n",
    "                rt += 1\r\n",
    "            ans += rt - lf - 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        dic = Counter(ages)\n",
    "        ages = [k for k in dic]\n",
    "        ages.sort()\n",
    "        n = len(ages)\n",
    "        ans = 0\n",
    "        pres = [0]\n",
    "        for age in ages:\n",
    "            pres.append(pres[-1] + dic[age])\n",
    "        for i in range(n):\n",
    "            if ages[i] < 15:\n",
    "                continue\n",
    "            idx = bisect.bisect_right(ages, 0.5*ages[i] + 7)\n",
    "            ans += (pres[i] - pres[idx])*dic[ages[i]] + dic[ages[i]]*(dic[ages[i]] - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(ages)\n",
    "        ages.sort(reverse=True)\n",
    "        res = 0\n",
    "        info = {}\n",
    "        for i, x in enumerate(ages):\n",
    "            if x <= 14:\n",
    "                break\n",
    "            if x in info:\n",
    "                res += info[x]\n",
    "                continue\n",
    "            r = n - 1\n",
    "            while i < r:\n",
    "                if 0.5 * x + 7 >= ages[r]:\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    res += r - i\n",
    "                    info[x] = r - i\n",
    "                    break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \"\"\"\n",
    "        f[y] > f[x] / 2 + 7\n",
    "        f[y] <= f[x]\n",
    "        f[y] <= 100 or f[x] >= 100\n",
    "        \"\"\"\n",
    "        \n",
    "        ages.sort()\n",
    "        print(ages)\n",
    "        cnt, n = 0, len(ages)\n",
    "        for x in range(n):\n",
    "            vmin = ages[x] * 0.5 + 7\n",
    "            vmax = ages[x] if ages[x] >= 100 else min(ages[x], 100)\n",
    "            ymin = bisect.bisect_right(ages, vmin)\n",
    "            ymax = bisect.bisect_right(ages, vmax)\n",
    "            cnt += max(0, ymax - ymin)\n",
    "            if ymin <= x < ymax:\n",
    "                cnt -= 1\n",
    "        return cnt\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        ages.sort()\n",
    "        left=right=len(ages)-1\n",
    "        res = 0\n",
    "        c = 0\n",
    "        while right >= 1:\n",
    "            while left>=0 and ages[left] > 0.5 * ages[right] + 7:\n",
    "                left -= 1\n",
    "            if ages[right] < 15:\n",
    "                return res\n",
    "            res += max(right - left - 1, 0)\n",
    "            right -= 1\n",
    "            if ages[right] == ages[right+1] and ages[right] >= 15:\n",
    "                c+=1\n",
    "                res += c\n",
    "            else:\n",
    "                c = 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        friendsage = lambda x : set(range(age+1-ceil(0.5*age-7), age+1))\n",
    "        aC, ans = Counter(ages), 0\n",
    "        for age in aC.keys():\n",
    "            if age > 14:\n",
    "                inS = (aC.keys() & friendsage(age)) # 交集\n",
    "                ans += (sum(aC[k] for k in inS) - 1)*aC[age]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        # have_send = {}\n",
    "        # ans = 0\n",
    "        # def check(x, y):\n",
    "        #     if y <= 0.5 * x + 7:\n",
    "        #         return False\n",
    "        #     if y > x:\n",
    "        #         return False\n",
    "        #     if y > 100 and x < 100:\n",
    "        #         return False\n",
    "        #     return True\n",
    "        # for i in range(len(ages)):\n",
    "        #     for j in range(len(ages)):\n",
    "        #         if i == j:\n",
    "        #             continue\n",
    "        #         if check(ages[i],ages[j]):\n",
    "        #             ans += 1\n",
    "        # return ans\n",
    "\n",
    "        ages.sort()\n",
    "        n = len(ages)\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        for i in range(n):\n",
    "            while(left < i and not self.check(ages[left],ages[i])):\n",
    "                left += 1\n",
    "\n",
    "            if right < i:\n",
    "                right = i\n",
    "\n",
    "            while(right < n and self.check(ages[right], ages[i])):\n",
    "                right += 1\n",
    "\n",
    "            if right > left:\n",
    "                ans += right - left - 1\n",
    "            \n",
    "        return ans\n",
    "\n",
    "    def check(self,x, y):\n",
    "            if y <= 0.5 * x + 7:\n",
    "                return False\n",
    "            if y > x:\n",
    "                return False\n",
    "            if y > 100 and x < 100:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "        n = len(ages)\n",
    "        ages.sort()\n",
    "        left = right = ans = 0\n",
    "        for age in ages:\n",
    "            if age < 15:\n",
    "                continue\n",
    "            while ages[left] <= 0.5 * age + 7:\n",
    "                left += 1\n",
    "            while right + 1 < n and ages[right + 1] <= age:\n",
    "                right += 1\n",
    "            ans += right - left\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numFriendRequests(self, ages: List[int]) -> int:\n",
    "\n",
    "        # ages[y] > 0.5*ages[x] + 7   => age[x] >= 15\n",
    "        # ages[y] <= ages[x]\n",
    "        # ages[y] <= 100 or ages[x] >=100\n",
    "\n",
    "        left = right = 0\n",
    "        n = len(ages)\n",
    "        ages.sort()\n",
    "        res = 0\n",
    "\n",
    "        for age in ages:\n",
    "            if age < 15:\n",
    "                continue\n",
    "\n",
    "            while ages[left] <=  0.5*age + 7:\n",
    "                left += 1\n",
    "\n",
    "            while right + 1 < n and ages[right+1] <= age:\n",
    "                right += 1\n",
    "\n",
    "            res += right - left\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
